const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 也称为“寻找循环的入口点”， 目的是给定一个可能包含环的链表，找出环的入口节点。如果链表中没有环，则返回 null。
// 思路，首先判断链表是否有环，slow和fast分别走一步和两步
// 如果有环的话，fast在绕环一圈后，必然在slow进入环的一圈内追上，
// 当fast追上slow的时候，该位置距离环的入口的距离等于从head到环入口的距离
function detectCycle(head) {
    if (!head || !head.next) {
        return null
    }
    let slow = head.next
    let fast = head.next.next
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return null
        }
        slow = slow.next
        fast = fast.next.next
    }
    slow = head
    while (slow !== fast) {
        slow = slow.next
        fast = fast.next
    }
    return slow
}

let node0 = new ListNode('abin')
let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node0.next = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1

console.log(detectCycle(node0))